package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-06-01 17:12
 */
public class 题库_0075_颜色分类 {

  static
  class Solution {
    public void sortColors(int[] nums) {
      if (nums == null || nums.length == 0) {
        return;
      }
      int index = 0;
      for (int i = 0; i < nums.length; ++i) {
        if (nums[i] == 0) {
          swap(nums, index, i);
          ++index;
        }
      }

      index = nums.length - 1;
      for (int i = nums.length - 1; i >= 0; --i) {
        if (nums[i] == 2) {
          swap(nums, index, i);
          --index;
        }
      }
    }

    public void sortColors1(int[] nums) {
      if (nums == null || nums.length == 0) {
        return;
      }
      int left = 0;
      int right = nums.length - 1;
      int index = 0;
      while (index <= right) {
        // left 指向第一个不等于 0 的位置
        while (left <= right && nums[left] == 0) {
          ++left;
        }

        // right 指向最后一个不等于 2 的位置
        while (right >= left && nums[right] == 2) {
          --right;
        }

        // index 指向 left ~ right 第一个等于 0 或 2 的位置
        if (index < left) {
          index = left;
        }
        while (index <= right && nums[index] == 1) {
          ++index;
        }

        if (left <= index && index <= right) {
          if (nums[index] == 0) {
            swap(nums, left, index);
          } else if (nums[index] == 2) {
            swap(nums, right, index);
          }
        }
      }
    }

    private void swap(int[] arr, int i, int j) {
      if (i != j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }

}
